use crate::q::Solution;

#[allow(unused)]
impl Solution {
    pub fn min_cut(s: String) -> i32 {
        // 方法1
        // 由于数据量太大，所以q131的回溯算法方式就不合适了
        // 这里有两个知识可以学习到
        // 第一个就是回文是可以用二位数组来记忆化，这样一来
        // 能够在O(1)的时间算出n长度的字符串中范围[i..j]是不是回文
        // 我们来看怎么做，首先我们需要一个n * n的二维数组，初始化为true，
        // 然后我们从长度2开始判断，因为长度1的字符自然都是符合条件的，
        // 这样我们逐步移动这个长度，就可以得到长度为2的所有字符串是否是回文，
        // 然后是长度是3，4…n，当长度大于2的时候，我们的子串就有多种了，
        // 那么子串怎么处理呢？子串的处理很简单，我们检查两头，如果相等，再缩小两头
        // 这样一来，长度是3的，就变成了1了，而长度是1的，自然都是回文，那就没问题
        // 长度是4的，就变成了2了，而长度是2的，我们在之前就判断过，如果是回文，那也没问题
        // 说起来稍微有点复杂，用一个例子来试试，例如: abacb，有个5个字符，我们的二维数组如下：
        //      0   1   2   3   4
        //   0  T   F   T   F
        //   1      T   F   F   F
        //   2          T   F   F
        //   3              T   F
        //   4                  T
        // 这里的(0,0)就表示了a，而(0,1)就表示了ab，自然(1,2)就表示了ba
        // 那么我们来依次填表，首先是长度1的，自然都是true
        // 然后是长度2的，0-1，ab不是，那么自然是false，1-2ba，也不是，2-3ac，3-4cb都不是
        // 然后是长度3的，0-2，aba，a和a是，然后1肯定是，所以是T，1-3bac，2-4acb都不是
        // 然后是长度4的，0-3，abac，a和c不对，1-4bacb，不是
        // 长度为5的我就不填了，这样可以从上表中看出来，我们实际上是从对角线开始斜着填表的
        // 以上是第一个知识。
        // 第二个就是dp的思想了，这里的子问题肯定就是某个子串了
        // 但是由于我们是分割整个字符串，我们总是需要判断0..i的，
        // 所以dp[i]就是0..i范围内的最小分割次数
        // 当然这里最基本的情况就是i是0的时候，dp[i] = 0
        // 或者0..i本身就是回文，那么也不需要分割
        // 那么，如果0..i不是回文的情况的话，我们如何推导这个状态转移方程
        // 这个时候我们随便找一个分割点j，这样就分成了0..j和j+1..i两个部分
        // 0..j我们知道就是dp[j]，那么如果j+1..i这个部分是回文的话
        // dp[i] = min(dp[i], dp[j] + 1)
        // 那么如果j+1..i这个部分不是回文的话，我们还需要再找分割点
        // 所以0..i的范围我们分割点从1开始逐渐分割
        // 最后dp[n - 1]就是结果，为啥呢？因为我们要整个字符串长度的结果，
        // 而dp[n - 1]存储的就是整个字符串长度的最小分割数
        // AC 8ms 4mb
        let n = s.len();
        let s = s.as_bytes();
        let mut is_palindrome = vec![vec![true; n]; n];
        for l in 2..=n {
            let mut i = 0;
            let mut j = i + l - 1;
            while j < n {
                is_palindrome[i][j] = s[i] == s[j] && is_palindrome[i + 1][j - 1];
                i += 1;
                j += 1;
            }
        }
        let mut dp = vec![n as i32; n];
        for i in 0..n {
            if is_palindrome[0][i] {
                dp[i] = 0;
                continue;
            }
            for j in 0..i {
                if is_palindrome[j + 1][i] {
                    dp[i] = dp[i].min(dp[j] + 1);
                }
            }
        }
        dp[n - 1]
    }
}